package com.code.leetcode._202504;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**三个数之和为零**/
public class ThreeNumAdd {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;//前后两个数一样的时候，减少循环次数
            int j = i + 1, k = n - 1;//第二个数从i+1 开始往后，第三个数从倒数第一个开始往前
            while (j < k) {//循环到折中的位置结束
                while (j > i + 1 && j < n && nums[j] == nums[j - 1]) j++;
                if (j >= k) break;
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                } else if (sum > 0) {//从小到大排序了，所以如果此时大于零了，后面肯定也会大于零
                    k--;
                } else if (sum < 0) {
                    j++;
                }
            }
        }
        return ans;
    }

}
